home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / POV-Ray 3.0.2 / src / SOURCE / lbuffer.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-18  |  29.7 KB  |  1,368 lines  |  [TEXT/MPS ]
  1. /****************************************************************************
  2. *                   lbuffer.c
  3. *
  4. *  This module implements functions that implement the light buffer.
  5. *
  6. *  This module was written by Dieter Bayer [DB].
  7. *
  8. *  from Persistence of Vision(tm) Ray Tracer
  9. *  Copyright 1996 Persistence of Vision Team
  10. *---------------------------------------------------------------------------
  11. *  NOTICE: This source code file is provided so that users may experiment
  12. *  with enhancements to POV-Ray and to port the software to platforms other
  13. *  than those supported by the POV-Ray Team.  There are strict rules under
  14. *  which you are permitted to use this file.  The rules are in the file
  15. *  named POVLEGAL.DOC which should be distributed with this file. If
  16. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  17. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  18. *  Forum.  The latest version of POV-Ray may be found there as well.
  19. *
  20. * This program is based on the popular DKB raytracer version 2.12.
  21. * DKBTrace was originally written by David K. Buck.
  22. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  23. *
  24. *****************************************************************************/
  25.  
  26. /****************************************************************************
  27. *
  28. *  Explanation:
  29. *
  30. *    -
  31. *
  32. *  ---
  33. *
  34. *  Mar 1994 : Creation.
  35. *
  36. *****************************************************************************/
  37.  
  38. #include "frame.h"
  39. #include "vector.h"
  40. #include "povproto.h"
  41. #include "point.h"
  42. #include "povray.h"
  43. #include "bbox.h"
  44. #include "lbuffer.h"
  45. #include "objects.h"
  46. #include "triangle.h"
  47. #include "vlbuffer.h"
  48.  
  49.  
  50.  
  51. /*****************************************************************************
  52. * Local preprocessor defines
  53. ******************************************************************************/
  54.  
  55.  
  56.  
  57. /*****************************************************************************
  58. * Local typedefs
  59. ******************************************************************************/
  60.  
  61.  
  62.  
  63. /*****************************************************************************
  64. * Local variabls
  65. ******************************************************************************/
  66.  
  67. /* Planes for 3d-clipping. */
  68.  
  69. static VECTOR VIEW_VX1 = {-0.7071067812, 0.0, -0.7071067812};
  70. static VECTOR VIEW_VX2 = { 0.7071067812, 0.0, -0.7071067812};
  71. static VECTOR VIEW_VY1 = {0.0, -0.7071067812, -0.7071067812};
  72. static VECTOR VIEW_VY2 = {0.0,  0.7071067812, -0.7071067812};
  73. static DBL VIEW_DX1 = 0.0;
  74. static DBL VIEW_DX2 = 0.0;
  75. static DBL VIEW_DY1 = 0.0;
  76. static DBL VIEW_DY2 = 0.0;
  77.  
  78.  
  79.  
  80. /*****************************************************************************
  81. * Static functions
  82. ******************************************************************************/
  83.  
  84. static void calc_points PARAMS((int Axis, OBJECT *Object, int *Number, VECTOR *Points, VECTOR Origin));
  85.  
  86. static int bbox_invisible PARAMS((int Axis, BBOX *BBox, VECTOR Origin));
  87.  
  88. static void project_rectangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible));
  89. static void project_triangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible));
  90. static void project_bbox PARAMS((PROJECT *Project, VECTOR *P, int *visible));
  91. static void project_object PARAMS((PROJECT *Project, OBJECT *Object, int Axis, VECTOR Origin));
  92.  
  93. static void project_bounding_slab PARAMS((int Axis, VECTOR Origin,
  94.   PROJECT *Project, PROJECT_TREE_NODE **Entry, BBOX_TREE *Node));
  95.  
  96.  
  97.  
  98. /*****************************************************************************
  99. *
  100. * FUNCTION
  101. *
  102. *   calc_points
  103. *
  104. * INPUT
  105. *
  106. *   Axis   - Axis along the objects will be projected
  107. *   Object - Object
  108. *   Number - Number of points to project
  109. *   Points - Points to project
  110. *   Origin - Origin of current light source
  111. *   
  112. * OUTPUT
  113. *
  114. *   Number, Points
  115. *   
  116. * RETURNS
  117. *   
  118. * AUTHOR
  119. *
  120. *   Dieter Bayer
  121. *   
  122. * DESCRIPTION
  123. *
  124. *   Calculate the points to project depending on the object type,
  125. *   the light source position and the axis. Note that only three
  126. *   points are used for triangles and eight for all other objects.
  127. *
  128. * CHANGES
  129. *
  130. *   May 1994 : Creation.
  131. *
  132. ******************************************************************************/
  133.  
  134. static void calc_points(Axis, Object, Number, Points, Origin)
  135. int Axis;
  136. OBJECT *Object;
  137. int *Number;
  138. VECTOR *Points, Origin;
  139. {
  140.   register int i;
  141.   DBL Direction;
  142.   VECTOR H[8];
  143.  
  144.   /* Get points depending on object's type */
  145.  
  146.   if ((Object->Methods != &Triangle_Methods) &&
  147.       (Object->Methods != &Smooth_Triangle_Methods))
  148.   {
  149.     *Number = 8;
  150.  
  151.     for (i = 0; i < 8; i++)
  152.     {
  153.       H[i][X] = ((i & 1) ? Object->BBox.Lengths[X] : 0.0) + Object->BBox.Lower_Left[X];
  154.       H[i][Y] = ((i & 2) ? Object->BBox.Lengths[Y] : 0.0) + Object->BBox.Lower_Left[Y];
  155.       H[i][Z] = ((i & 4) ? Object->BBox.Lengths[Z] : 0.0) + Object->BBox.Lower_Left[Z];
  156.     }
  157.   }
  158.   else
  159.   {
  160.     if (Object->Methods == &Triangle_Methods)
  161.     {
  162.       *Number = 3;
  163.  
  164.       Assign_Vector(H[0], ((TRIANGLE *)Object)->P1);
  165.       Assign_Vector(H[1], ((TRIANGLE *)Object)->P2);
  166.       Assign_Vector(H[2], ((TRIANGLE *)Object)->P3);
  167.     }
  168.  
  169.     if (Object->Methods == &Smooth_Triangle_Methods)
  170.     {
  171.       *Number = 3;
  172.  
  173.       Assign_Vector(H[0], ((SMOOTH_TRIANGLE *)Object)->P1);
  174.       Assign_Vector(H[1], ((SMOOTH_TRIANGLE *)Object)->P2);
  175.       Assign_Vector(H[2], ((SMOOTH_TRIANGLE *)Object)->P3);
  176.     }
  177.   }
  178.  
  179.   /* Modify points so that the new z direction is the projection axis. */
  180.  
  181.   if ((Axis == XaxisP) || (Axis == YaxisP) || (Axis == ZaxisP))
  182.   {
  183.     Direction = 1.0;
  184.   }
  185.   else
  186.   {
  187.     Direction = -1.0;
  188.   }
  189.  
  190.   switch (Axis)
  191.   {
  192.     case XaxisP :
  193.     case XaxisM :
  194.  
  195.       for (i = 0; i < *Number; i++)
  196.       {
  197.         Points[i][X] = (H[i][Y] - Origin[Y]);
  198.         Points[i][Y] = (H[i][Z] - Origin[Z]);
  199.         Points[i][Z] = (H[i][X] - Origin[X]) * Direction;
  200.       }
  201.  
  202.       break;
  203.  
  204.     case YaxisP :
  205.     case YaxisM :
  206.  
  207.       for (i = 0; i < *Number; i++)
  208.       {
  209.         Points[i][X] = (H[i][X] - Origin[X]);
  210.         Points[i][Y] = (H[i][Z] - Origin[Z]);
  211.         Points[i][Z] = (H[i][Y] - Origin[Y]) * Direction;
  212.       }
  213.  
  214.       break;
  215.  
  216.     case ZaxisP :
  217.     case ZaxisM :
  218.  
  219.       for (i = 0; i < *Number; i++)
  220.       {
  221.         Points[i][X] = (H[i][X] - Origin[X]);
  222.         Points[i][Y] = (H[i][Y] - Origin[Y]);
  223.         Points[i][Z] = (H[i][Z] - Origin[Z]) * Direction;
  224.       }
  225.  
  226.       break;
  227.  
  228.     default : Error("Illegal axis in module calc_points() in lbuffer.c.\n");
  229.   }
  230. }
  231.  
  232.  
  233.  
  234. /*****************************************************************************
  235. *
  236. * FUNCTION
  237. *
  238. *   bbox_invisible
  239. *
  240. * INPUT
  241. *
  242. *   Axis   - Axis along the objects will be projected
  243. *   BBox   - Bounding box to test
  244. *   Origin - Origin of current light source
  245. *
  246. * OUTPUT
  247. *
  248. * RETURNS
  249. *
  250. *   int - Flag if bounding box is totally invisble
  251. *
  252. * AUTHOR
  253. *
  254. *   Dieter Bayer
  255. *
  256. * DESCRIPTION
  257. *
  258. *   Do a quick test if a bounding box is totally invisble from the
  259. *   current light source in the specified axis direction.
  260. *
  261. * CHANGES
  262. *
  263. *   May 1994 : Creation.
  264. *
  265. ******************************************************************************/
  266.  
  267. static int bbox_invisible(Axis, BBox, Origin)
  268. int Axis;
  269. BBOX *BBox;
  270. VECTOR Origin;
  271. {
  272.   DBL x1, y1, z1, x2, y2, z2, x, y, z;
  273.  
  274.   switch (Axis)
  275.   {
  276.     case XaxisP :
  277.  
  278.       /* Bounding box behind light source? */
  279.  
  280.       if ((x = BBox->Lower_Left[X] + BBox->Lengths[X] - Origin[X]) <= 0.0)
  281.       {
  282.         return(TRUE);
  283.       }
  284.  
  285.       /* Bounding box on the right/left side? */
  286.  
  287.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  288.       y2 = y1 + BBox->Lengths[Y];
  289.  
  290.       if (((y1 > 0.0) && (y1 > x)) || ((y2 < 0.0) && (-y2 > x)))
  291.       {
  292.         return(TRUE);
  293.       }
  294.  
  295.       /* Bounding box on the bottom/top side? */
  296.  
  297.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  298.       z2 = z1 + BBox->Lengths[Z];
  299.  
  300.       if (((z1 > 0.0) && (z1 > x)) || ((z2 < 0.0) && (-z2 > x)))
  301.       {
  302.         return(TRUE);
  303.       }
  304.  
  305.       break;
  306.  
  307.     case XaxisM :
  308.  
  309.       /* Bounding box behind light source? */
  310.  
  311.       if ((x = BBox->Lower_Left[X] - Origin[X]) >= 0.0)
  312.       {
  313.         return(TRUE);
  314.       }
  315.  
  316.       /* Bounding box on the right/left side? */
  317.  
  318.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  319.       y2 = y1 + BBox->Lengths[Y];
  320.  
  321.       if (((y1 > 0.0) && (y1 > -x)) || ((y2 < 0.0) && (y2 < x)))
  322.       {
  323.         return(TRUE);
  324.       }
  325.  
  326.       /* Bounding box on the bottom/top side? */
  327.  
  328.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  329.       z2 = z1 + BBox->Lengths[Z];
  330.  
  331.       if (((z1 > 0.0) && (z1 > -x)) || ((z2 < 0.0) && (z2 < x)))
  332.       {
  333.         return(TRUE);
  334.       }
  335.  
  336.       break;
  337.  
  338.     case YaxisP :
  339.  
  340.       /* Bounding box behind light source? */
  341.  
  342.       if ((y = BBox->Lower_Left[Y] + BBox->Lengths[Y] - Origin[Y]) <= 0.0)
  343.       {
  344.         return(TRUE);
  345.       }
  346.  
  347.       /* Bounding box on the right/left side? */
  348.  
  349.       x1 = BBox->Lower_Left[X] - Origin[X];
  350.       x2 = x1 + BBox->Lengths[X];
  351.  
  352.       if (((x1 > 0.0) && (x1 > y)) || ((x2 < 0.0) && (-x2 > y)))
  353.       {
  354.         return(TRUE);
  355.       }
  356.  
  357.       /* Bounding box on the bottom/top side? */
  358.  
  359.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  360.       z2 = z1 + BBox->Lengths[Z];
  361.  
  362.       if (((z1 > 0.0) && (z1 > y)) || ((z2 < 0.0) && (-z2 > y)))
  363.       {
  364.         return(TRUE);
  365.       }
  366.  
  367.       break;
  368.  
  369.     case YaxisM :
  370.  
  371.       /* Bounding box behind light source? */
  372.  
  373.       if ((y = BBox->Lower_Left[Y] - Origin[Y]) >= 0.0)
  374.       {
  375.         return(TRUE);
  376.       }
  377.  
  378.       /* Bounding box on the right/left side? */
  379.  
  380.       x1 = BBox->Lower_Left[X] - Origin[X];
  381.       x2 = x1 + BBox->Lengths[X];
  382.  
  383.       if (((x1 > 0.0) && (x1 > -y)) || ((x2 < 0.0) && (x2 < y)))
  384.       {
  385.         return(TRUE);
  386.       }
  387.  
  388.       /* Bounding box on the bottom/top side? */
  389.  
  390.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  391.       z2 = z1 + BBox->Lengths[Z];
  392.  
  393.       if (((z1 > 0.0) && (z1 > -y)) || ((z2 < 0.0) && (z2 < y)))
  394.       {
  395.         return(TRUE);
  396.       }
  397.  
  398.       break;
  399.  
  400.     case ZaxisP :
  401.  
  402.       /* Bounding box behind light source? */
  403.  
  404.       if ((z = BBox->Lower_Left[Z] + BBox->Lengths[Z] - Origin[Z]) <= 0.0)
  405.       {
  406.         return(TRUE);
  407.       }
  408.  
  409.       /* Bounding box on the right/left side? */
  410.  
  411.       x1 = BBox->Lower_Left[X] - Origin[X];
  412.       x2 = x1 + BBox->Lengths[X];
  413.  
  414.       if (((x1 > 0.0) && (x1 > z)) || ((x2 < 0.0) && (-x2 > z)))
  415.       {
  416.         return(TRUE);
  417.       }
  418.  
  419.       /* Bounding box on the bottom/top side? */
  420.  
  421.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  422.       y2 = y1 + BBox->Lengths[Y];
  423.  
  424.       if (((y1 > 0.0) && (y1 > z)) || ((y2 < 0.0) && (-y2 > z)))
  425.       {
  426.         return(TRUE);
  427.       }
  428.  
  429.       break;
  430.  
  431.     case ZaxisM :
  432.  
  433.       /* Bounding box behind light source? */
  434.  
  435.       if ((z = BBox->Lower_Left[Z] - Origin[Z]) >= 0.0)
  436.       {
  437.         return(TRUE);
  438.       }
  439.  
  440.       /* Bounding box on the right/left side? */
  441.  
  442.       x1 = BBox->Lower_Left[X] - Origin[X];
  443.       x2 = x1 + BBox->Lengths[X];
  444.  
  445.       if (((x1 > 0.0) && (x1 > -z)) || ((x2 < 0.0) && (x2 < z)))
  446.       {
  447.         return(TRUE);
  448.       }
  449.  
  450.       /* Bounding box on the bottom/top side? */
  451.  
  452.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  453.       y2 = y1 + BBox->Lengths[Y];
  454.  
  455.       if (((y1 > 0.0) && (y1 > -z)) || ((y2 < 0.0) && (y2 < z)))
  456.       {
  457.         return(TRUE);
  458.       }
  459.  
  460.       break;
  461.  
  462.     default :
  463.  
  464.       Error("Illegal axis in bbox_invisible() in lbuffer.c.\n");
  465.   }
  466.  
  467.   return(FALSE);
  468. }
  469.  
  470.  
  471.  
  472. /*****************************************************************************
  473. *
  474. * FUNCTION
  475. *
  476. *   project_rectangle
  477. *
  478. * INPUT
  479. *
  480. *   Project        - Rectangle's projection
  481. *   P1, P2, P3, P4 - Rectangle's edges
  482. *   visible        - Flag if rectangle is visible
  483. *
  484. * OUTPUT
  485. *
  486. *   Project, visible
  487. *   
  488. * RETURNS
  489. *   
  490. * AUTHOR
  491. *
  492. *   Dieter Bayer
  493. *   
  494. * DESCRIPTION
  495. *
  496. *   Project a rectangle onto a light source.
  497. *
  498. * CHANGES
  499. *
  500. *   May 1994 : Creation.
  501. *
  502. ******************************************************************************/
  503.  
  504. static void project_rectangle(Project, P1, P2, P3, P4, visible)
  505. PROJECT *Project;
  506. VECTOR P1, P2, P3, P4;
  507. int *visible;
  508. {
  509.   VECTOR Points[MAX_CLIP_POINTS];
  510.   int i, number;
  511.   int x, y;
  512.  
  513.   Assign_Vector(Points[0], P1);
  514.   Assign_Vector(Points[1], P2);
  515.   Assign_Vector(Points[2], P3);
  516.   Assign_Vector(Points[3], P4);
  517.  
  518.   number = 4;
  519.  
  520.   Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
  521.                                 VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
  522.  
  523.   if (number)
  524.   {
  525.     for (i = 0; i < number; i++)
  526.     {
  527.       if (Points[i][Z] < EPSILON)
  528.       {
  529.         Points[i][X] = Points[i][Y] = 0.0;
  530.       }
  531.       else
  532.       {
  533.         Points[i][X] /= Points[i][Z];
  534.         Points[i][Y] /= Points[i][Z];
  535.  
  536.         if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
  537.         if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
  538.       }
  539.  
  540.       x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
  541.       y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
  542.  
  543.       if (x < Project->x1) Project->x1 = x;
  544.       if (x > Project->x2) Project->x2 = x;
  545.       if (y < Project->y1) Project->y1 = y;
  546.       if (y > Project->y2) Project->y2 = y;
  547.     }
  548.  
  549.     *visible = TRUE;
  550.   }
  551. }
  552.  
  553.  
  554.  
  555.  
  556. /*****************************************************************************
  557. *
  558. * FUNCTION
  559. *
  560. *   project_triangle
  561. *
  562. * INPUT
  563. *
  564. *   Project    - Triangle's projection
  565. *   P1, P2, P3 - Triangles's edges
  566. *   visible    - Flag if triangle is visible
  567. *   
  568. * OUTPUT
  569. *
  570. *   Project, visible
  571. *   
  572. * RETURNS
  573. *   
  574. * AUTHOR
  575. *
  576. *   Dieter Bayer
  577. *   
  578. * DESCRIPTION
  579. *
  580. *   Project a triangle onto a light source.
  581. *
  582. * CHANGES
  583. *
  584. *   May 1994 : Creation.
  585. *
  586. ******************************************************************************/
  587.  
  588. static void project_triangle(Project, P1, P2, P3, visible)
  589. PROJECT *Project;
  590. VECTOR P1, P2, P3;
  591. int *visible;
  592. {
  593.   VECTOR Points[MAX_CLIP_POINTS];
  594.   int i, number;
  595.   int x, y, clip;
  596.  
  597.   clip = TRUE;
  598.  
  599.   /* Check if all points lie "in front" of the light source. */
  600.  
  601.   if ((P1[Z] > 0.0) && (P2[Z] > 0.0) && (P3[Z] > 0.0))
  602.   {
  603.     /* Check if all points lie inside the "viewing pyramid". */
  604.  
  605.     if ((fabs(P1[X]) <= P1[Z]) && (fabs(P2[X]) <= P2[Z]) && (fabs(P3[X]) <= P3[Z]) &&
  606.         (fabs(P1[Y]) <= P1[Z]) && (fabs(P2[Y]) <= P2[Z]) && (fabs(P3[Y]) <= P3[Z]))
  607.     {
  608.       /* No clipping is needed. Just project the points. */
  609.  
  610.       clip = FALSE;
  611.     }
  612.     else
  613.     {
  614.       /* Check if all points lie on the "right side". */
  615.  
  616.       if ((P1[X] > 0.0) && (P1[X] > P1[Z]) &&
  617.           (P2[X] > 0.0) && (P2[X] > P2[Z]) &&
  618.           (P3[X] > 0.0) && (P3[X] > P3[Z]))
  619.       {
  620.         return;
  621.       }
  622.  
  623.       /* Check if all points lie on the "left side". */
  624.  
  625.       if ((P1[X] < 0.0) && (-P1[X] > P1[Z]) &&
  626.           (P2[X] < 0.0) && (-P2[X] > P2[Z]) &&
  627.           (P3[X] < 0.0) && (-P3[X] > P3[Z]))
  628.       {
  629.         return;
  630.       }
  631.  
  632.       /* Check if all points lie above the "top side". */
  633.  
  634.       if ((P1[Y] > 0.0) && (P1[Y] > P1[Z]) &&
  635.           (P2[Y] > 0.0) && (P2[Y] > P2[Z]) &&
  636.           (P3[Y] > 0.0) && (P3[Y] > P3[Z]))
  637.       {
  638.         return;
  639.       }
  640.  
  641.       /* Check if all points lie below the "bottom side". */
  642.  
  643.       if ((P1[Y] < 0.0) && (-P1[Y] > P1[Z]) &&
  644.           (P2[Y] < 0.0) && (-P2[Y] > P2[Z]) &&
  645.           (P3[Y] < 0.0) && (-P3[Y] > P3[Z]))
  646.       {
  647.         return;
  648.       }
  649.     }
  650.   }
  651.  
  652.   Assign_Vector(Points[0], P1);
  653.   Assign_Vector(Points[1], P2);
  654.   Assign_Vector(Points[2], P3);
  655.  
  656.   number = 3;
  657.  
  658.   if (clip)
  659.   {
  660.     Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
  661.                                   VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
  662.   }
  663.  
  664.   if (number)
  665.   {
  666.     for (i = 0; i < number; i++)
  667.     {
  668.       if (fabs(Points[i][Z]) < EPSILON)
  669.       {
  670.         Points[i][X] = Points[i][Y] = 0.0;
  671.       }
  672.       else
  673.       {
  674.         Points[i][X] /= Points[i][Z];
  675.         Points[i][Y] /= Points[i][Z];
  676.  
  677.         if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
  678.         if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
  679.       }
  680.  
  681.       x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
  682.       y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
  683.  
  684.       if (x < Project->x1) Project->x1 = x;
  685.       if (x > Project->x2) Project->x2 = x;
  686.       if (y < Project->y1) Project->y1 = y;
  687.       if (y > Project->y2) Project->y2 = y;
  688.     }
  689.  
  690.     *visible = TRUE;
  691.   }
  692. }
  693.  
  694.  
  695.  
  696.  
  697. /*****************************************************************************
  698. *
  699. * FUNCTION
  700. *
  701. *   Project_BBox
  702. *
  703. * INPUT
  704. *
  705. *   Project - Box's projection
  706. *   P       - Box's edges
  707. *   visible - Flag if box is visible
  708. *   
  709. * OUTPUT
  710. *
  711. *   Project, visible
  712. *   
  713. * RETURNS
  714. *   
  715. * AUTHOR
  716. *
  717. *   Dieter Bayer
  718. *   
  719. * DESCRIPTION
  720. *
  721. *   Project an axis-aligned box onto a light source.
  722. *
  723. * CHANGES
  724. *
  725. *   May 1994 : Creation.
  726. *
  727. ******************************************************************************/
  728.  
  729. static void project_bbox(Project, P, visible)
  730. PROJECT *Project;
  731. VECTOR *P;
  732. int *visible;
  733. {
  734.   int i, x, y;
  735.  
  736.   /* Check if all points lie "in front" of the light source. */
  737.  
  738.   if ((P[0][Z] > 0.0) && (P[1][Z] > 0.0) && (P[2][Z] > 0.0) && (P[3][Z] > 0.0) &&
  739.       (P[4][Z] > 0.0) && (P[5][Z] > 0.0) && (P[6][Z] > 0.0) && (P[7][Z] > 0.0))
  740.   {
  741.     /* Check if all points lie inside the "viewing pyramid". */
  742.  
  743.     if ((fabs(P[0][X]) <= P[0][Z]) && (fabs(P[1][X]) <= P[1][Z]) &&
  744.         (fabs(P[2][X]) <= P[2][Z]) && (fabs(P[3][X]) <= P[3][Z]) &&
  745.         (fabs(P[4][X]) <= P[4][Z]) && (fabs(P[5][X]) <= P[5][Z]) &&
  746.         (fabs(P[6][X]) <= P[6][Z]) && (fabs(P[7][X]) <= P[7][Z]) &&
  747.         (fabs(P[0][Y]) <= P[0][Z]) && (fabs(P[1][Y]) <= P[1][Z]) &&
  748.         (fabs(P[2][Y]) <= P[2][Z]) && (fabs(P[3][Y]) <= P[3][Z]) &&
  749.         (fabs(P[4][Y]) <= P[4][Z]) && (fabs(P[5][Y]) <= P[5][Z]) &&
  750.         (fabs(P[6][Y]) <= P[6][Z]) && (fabs(P[7][Y]) <= P[7][Z]))
  751.     {
  752.       /* No clipping is needed. Just project the points. */
  753.  
  754.       for (i = 0; i < 8; i++)
  755.       {
  756.         if (P[i][Z] < EPSILON)
  757.         {
  758.           P[i][X] = P[i][Y] = 0.0;
  759.         }
  760.         else
  761.         {
  762.           P[i][X] /= P[i][Z];
  763.           P[i][Y] /= P[i][Z];
  764.  
  765.           if (fabs(P[i][X]) < EPSILON) P[i][X] = 0.0;
  766.           if (fabs(P[i][Y]) < EPSILON) P[i][Y] = 0.0;
  767.         }
  768.  
  769.         x = (int)(MAX_BUFFER_ENTRY * P[i][X]);
  770.         y = (int)(MAX_BUFFER_ENTRY * P[i][Y]);
  771.  
  772.         if (x < Project->x1) Project->x1 = x;
  773.         if (x > Project->x2) Project->x2 = x;
  774.         if (y < Project->y1) Project->y1 = y;
  775.         if (y > Project->y2) Project->y2 = y;
  776.       }
  777.  
  778.       *visible = TRUE;
  779.  
  780.       return;
  781.     }
  782.     else
  783.     {
  784.       /* Check if all points lie on the "right side". */
  785.  
  786.       for (i = 0; i < 8; i++)
  787.       {
  788.         if ((P[i][X] < 0.0) || (P[i][X] <= P[i][Z])) break;
  789.       }
  790.  
  791.       if (i == 8) return;
  792.  
  793.       /* Check if all points lie on the "left side". */
  794.  
  795.       for (i = 0; i < 8; i++)
  796.       {
  797.         if ((P[i][X] > 0.0) || (-P[i][X] <= P[i][Z])) break;
  798.       }
  799.  
  800.       if (i == 8) return;
  801.  
  802.       /* Check if all points lie above the "top side". */
  803.  
  804.       for (i = 0; i < 8; i++)
  805.       {
  806.         if ((P[i][Y] < 0.0) || (P[i][Y] <= P[i][Z])) break;
  807.       }
  808.  
  809.       if (i == 8) return;
  810.  
  811.       /* Check if all points lie below the "bottom side". */
  812.  
  813.       for (i = 0; i < 8; i++)
  814.       {
  815.         if ((P[i][Y] > 0.0) || (-P[i][Y] <= P[i][Z])) break;
  816.       }
  817.  
  818.       if (i == 8) return;
  819.     }
  820.   }
  821.  
  822.   project_rectangle(Project, P[0], P[1], P[3], P[2], visible);
  823.   project_rectangle(Project, P[4], P[5], P[7], P[6], visible);
  824.   project_rectangle(Project, P[0], P[1], P[5], P[4], visible);
  825.   project_rectangle(Project, P[2], P[3], P[7], P[6], visible);
  826.   project_rectangle(Project, P[1], P[3], P[7], P[5], visible);
  827.   project_rectangle(Project, P[0], P[2], P[6], P[4], visible);
  828. }
  829.  
  830.  
  831.  
  832. /*****************************************************************************
  833. *
  834. * FUNCTION
  835. *
  836. *   project_object
  837. *
  838. * INPUT
  839. *
  840. *   Object   - Object to project
  841. *   Project  - Projection
  842. *   
  843. * OUTPUT
  844. *
  845. *   Project
  846. *
  847. * RETURNS
  848. *   
  849. * AUTHOR
  850. *
  851. *   Dieter Bayer
  852. *   
  853. * DESCRIPTION
  854. *
  855. *   Get the projection of a single object onto a light source.
  856. *
  857. * CHANGES
  858. *
  859. *   May 1994 : Creation.
  860. *
  861. ******************************************************************************/
  862.  
  863. static void project_object(Project, Object, Axis, Origin)
  864. PROJECT *Project;
  865. OBJECT *Object;
  866. int Axis;
  867. VECTOR Origin;
  868. {
  869.   int visible, Number;
  870.   VECTOR Points[8];
  871.  
  872.   /* Do not project infinite objects (always visible!) */
  873.  
  874.   if (Test_Flag(Object, INFINITE_FLAG))
  875.   {
  876.     Project->x1 = Project->y1 = MIN_BUFFER_ENTRY;
  877.     Project->x2 = Project->y2 = MAX_BUFFER_ENTRY;
  878.  
  879.     return;
  880.   }
  881.  
  882.   /* Get points to project */
  883.  
  884.   calc_points(Axis, Object, &Number, Points, Origin);
  885.  
  886.   visible = FALSE;
  887.  
  888.   Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
  889.   Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
  890.  
  891.   if (Number == 3)
  892.   {
  893.     project_triangle(Project, Points[0], Points[1], Points[2], &visible);
  894.   }
  895.   else
  896.   {
  897.     project_bbox(Project, Points, &visible);
  898.   }
  899.  
  900.   if (!visible)
  901.   {
  902.     /* Object is invisible */
  903.  
  904.     Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
  905.     Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
  906.   }
  907.   else
  908.   {
  909.     /* We don't want to miss something */
  910.  
  911.     Project->x1 -= 2;
  912.     Project->x2 += 2;
  913.     Project->y1 -= 2;
  914.     Project->y2 += 2;
  915.   }
  916. }
  917.  
  918.  
  919.  
  920. /*****************************************************************************
  921. *
  922. * FUNCTION
  923. *
  924. *   project_bounding_slab
  925. *
  926. * INPUT
  927. *
  928. *   Axis     - Axis along the objects will be projected
  929. *   Origin   - Origin of current light source
  930. *   Project  - Projection
  931. *   Tree     - Current node/leaf
  932. *   Object   - Node/leaf in bounding slab hierarchy
  933. *   
  934. * OUTPUT
  935. *
  936. *   Project, Tree
  937. *   
  938. * RETURNS
  939. *   
  940. * AUTHOR
  941. *
  942. *   Dieter Bayer
  943. *   
  944. * DESCRIPTION
  945. *
  946. *   Project the bounding slab hierarchy onto a light source and thus create
  947. *   the light buffer hierarchy for this light source.
  948. *
  949. * CHANGES
  950. *
  951. *   May 1994 : Creation.
  952. *
  953. ******************************************************************************/
  954.  
  955. static void project_bounding_slab(Axis, Origin, Project, Tree, Node)
  956. int Axis;
  957. VECTOR Origin;
  958. PROJECT *Project;
  959. PROJECT_TREE_NODE **Tree;
  960. BBOX_TREE *Node;
  961. {
  962.   short int i;
  963.   PROJECT Temp;
  964.   PROJECT_TREE_LEAF *Leaf;
  965.   PROJECT_TREE_NODE New;
  966.  
  967.   COOPERATE_1
  968.  
  969.   /* If the node is totally invisible we are ready. */
  970.  
  971.   if (bbox_invisible(Axis, &Node->BBox, Origin))
  972.   {
  973.     return;
  974.   }
  975.  
  976.   if (Node->Entries)
  977.   {
  978.     /* Current object is a bounding object, i.e. a node in the slab tree. */
  979.  
  980.     /* First, Init new entry. */
  981.  
  982.     New.Entries = 0;
  983.  
  984.     New.Node = Node;
  985.  
  986.     New.Project.x1 = New.Project.y1 = MAX_BUFFER_ENTRY;
  987.     New.Project.x2 = New.Project.y2 = MIN_BUFFER_ENTRY;
  988.  
  989.     /* Allocate temporary memory for node/leaf entries. */
  990.  
  991.     New.Entry = (PROJECT_TREE_NODE **)POV_MALLOC(Node->Entries*sizeof(PROJECT_TREE_NODE *), "temporary tree entry");
  992.  
  993.     /* This is no leaf, it's a node. */
  994.  
  995.     New.is_leaf = FALSE;
  996.  
  997.     /* Second, Get new entry, i.e. project bounding slab's entries. */
  998.  
  999.     for (i = 0; i < Node->Entries; i++)
  1000.     {
  1001.       New.Entry[i] = NULL;
  1002.  
  1003.       project_bounding_slab(Axis, Origin, &Temp, &New.Entry[New.Entries], Node->Node[i]);
  1004.  
  1005.       /* Use only visible entries. */
  1006.  
  1007.       if (New.Entry[New.Entries] != NULL)
  1008.       {
  1009.         New.Project.x1 = min(New.Project.x1, Temp.x1);
  1010.         New.Project.x2 = max(New.Project.x2, Temp.x2);
  1011.         New.Project.y1 = min(New.Project.y1, Temp.y1);
  1012.         New.Project.y2 = max(New.Project.y2, Temp.y2);
  1013.  
  1014.         New.Entries++;
  1015.       }
  1016.     }
  1017.  
  1018.     /* If there are any visible entries, we'll use them. */
  1019.  
  1020.     if (New.Entries > 0)
  1021.     {
  1022.       /* If there's only one entry, we won't need a new node. */
  1023.  
  1024.       if (New.Entries == 1)
  1025.       {
  1026.         *Tree    = New.Entry[0];
  1027.         *Project = New.Project;
  1028.       }
  1029.       else
  1030.       {
  1031.         /* Allocate memory for new node in the light tree. */
  1032.  
  1033.         *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_NODE), "light tree node");
  1034.  
  1035.         **Tree = New;
  1036.  
  1037.         /* Allocate memory for node/leaf entries. */
  1038.  
  1039.         (*Tree)->Entry = (PROJECT_TREE_NODE **)POV_MALLOC(New.Entries*sizeof(PROJECT_TREE_NODE *), "light tree node");
  1040.  
  1041.         memcpy((*Tree)->Entry, New.Entry, New.Entries*sizeof(PROJECT_TREE_NODE *));
  1042.  
  1043.         *Project = New.Project;
  1044.       }
  1045.     }
  1046.  
  1047.     /* Get rid of temporary node/leaf entries. */
  1048.  
  1049.     POV_FREE(New.Entry);
  1050.   }
  1051.   else
  1052.   {
  1053.     /* Current object is a normal object, i.e. a leaf in the slab tree. */
  1054.  
  1055.     /* If object doesn't cast shadows we can skip. */
  1056.  
  1057.     if (!Test_Flag((OBJECT *)Node->Node, NO_SHADOW_FLAG))
  1058.     {
  1059.       /* Project object onto light source. */
  1060.  
  1061.       project_object(Project, (OBJECT *)Node->Node, Axis, Origin);
  1062.  
  1063.       /* Is the object visible? */
  1064.  
  1065.       if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2))
  1066.       {
  1067.         /* Allocate memory for new leaf in the light tree. */
  1068.  
  1069.         *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_LEAF), "light tree leaf");
  1070.  
  1071.         /* Init new leaf. */
  1072.  
  1073.         Leaf = (PROJECT_TREE_LEAF *)(*Tree);
  1074.  
  1075.         Leaf->Node = Node;
  1076.  
  1077.         Leaf->Project = *Project;
  1078.  
  1079.         /* Yes, this is a leaf. */
  1080.  
  1081.         Leaf->is_leaf = TRUE;
  1082.       }
  1083.     }
  1084.   }
  1085. }
  1086.  
  1087.  
  1088.  
  1089. /*****************************************************************************
  1090. *
  1091. * FUNCTION
  1092. *
  1093. *   Build_Light_Buffers
  1094. *
  1095. * INPUT
  1096. *   
  1097. * OUTPUT
  1098. *   
  1099. * RETURNS
  1100. *   
  1101. * AUTHOR
  1102. *
  1103. *   Dieter Bayer
  1104. *   
  1105. * DESCRIPTION
  1106. *
  1107. *   Build the light buffers, i.e. the 2d representations of the bounding slab
  1108. *   hierarchy seen from the light sources.
  1109. *
  1110. * CHANGES
  1111. *
  1112. *   May 1994 : Creation.
  1113. *
  1114. ******************************************************************************/
  1115.  
  1116. void Build_Light_Buffers()
  1117. {
  1118.   int Axis;
  1119.   PROJECT Project;
  1120.   LIGHT_SOURCE *Light;
  1121.  
  1122.   if (!(opts.Quality_Flags & Q_SHADOW) || (!opts.Use_Slabs))
  1123.   {
  1124.     opts.Options &= ~USE_LIGHT_BUFFER;
  1125.   }
  1126.  
  1127.   if (opts.Options & USE_LIGHT_BUFFER)
  1128.   {
  1129.     Status_Info("\nCreating light buffers");
  1130.     
  1131.     /* Build the light buffer for all point(!) light sources */
  1132.   
  1133.     for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
  1134.     {
  1135.       if ((!Light->Area_Light) && (Light->Light_Type!=FILL_LIGHT_SOURCE))
  1136.       {
  1137.         Status_Info(".");
  1138.     
  1139.         /* Project bounding slabs on all six sides */
  1140.   
  1141.         for (Axis = 0; Axis < 6; Axis++)
  1142.         {
  1143.           Light->Light_Buffer[Axis] = NULL;
  1144.   
  1145.           project_bounding_slab(Axis, Light->Center, &Project,
  1146.             &Light->Light_Buffer[Axis], Root_Object);
  1147.         }
  1148.       }
  1149.     }
  1150.   }
  1151. }
  1152.  
  1153.  
  1154.  
  1155. /*****************************************************************************
  1156. *
  1157. * FUNCTION
  1158. *
  1159. *   Destroy_Light_Buffers
  1160. *
  1161. * INPUT
  1162. *   
  1163. * OUTPUT
  1164. *   
  1165. * RETURNS
  1166. *   
  1167. * AUTHOR
  1168. *
  1169. *   Dieter Bayer
  1170. *   
  1171. * DESCRIPTION
  1172. *
  1173. *   Destroy the light buffers.
  1174. *
  1175. * CHANGES
  1176. *
  1177. *   Sep 1994 : Creation.
  1178. *
  1179. ******************************************************************************/
  1180.  
  1181. void Destroy_Light_Buffers()
  1182. {
  1183.   int Axis;
  1184.   LIGHT_SOURCE *Light;
  1185.  
  1186.   if (opts.Options & USE_LIGHT_BUFFER)
  1187.   {
  1188.     for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
  1189.     {
  1190.       if ((!Light->Area_Light) && (Light->Light_Type!=FILL_LIGHT_SOURCE))
  1191.       {
  1192.         for (Axis = 0; Axis < 6; Axis++)
  1193.         {
  1194.           if (Light->Light_Buffer[Axis] != NULL)
  1195.           {
  1196.             Destroy_Project_Tree(Light->Light_Buffer[Axis]);
  1197.           }
  1198.  
  1199.           Light->Light_Buffer[Axis] = NULL;
  1200.         }
  1201.       }
  1202.     }
  1203.   }
  1204. }
  1205.  
  1206.  
  1207.  
  1208. /*****************************************************************************
  1209. *
  1210. * FUNCTION
  1211. *
  1212. *   Intersect_Light_Tree
  1213. *
  1214. * INPUT
  1215. *
  1216. *   Ray               - Shadow ray
  1217. *   Tree              - Light tree's top-node
  1218. *   x                 - X-coordinate of the shadow ray
  1219. *   y                 - Y-coordinate of the shadow ray
  1220. *   Best_Intersection - Intersection found
  1221. *   Best_Object       - Object found
  1222. *   
  1223. * OUTPUT
  1224. *
  1225. *   Best_Intersection, Best_Object
  1226. *   
  1227. * RETURNS
  1228. *   
  1229. * AUTHOR
  1230. *
  1231. *   Dieter Bayer
  1232. *
  1233. * DESCRIPTION
  1234. *
  1235. *   Intersect a shadow ray with the light tree
  1236. *   (same as for the vista tree but without pruning).
  1237. *
  1238. * CHANGES
  1239. *
  1240. *   May 1994 : Creation.
  1241. *
  1242. ******************************************************************************/
  1243.  
  1244. int Intersect_Light_Tree(Ray, Tree, x, y, Best_Intersection, Best_Object)
  1245. RAY *Ray;
  1246. PROJECT_TREE_NODE *Tree;
  1247. int x, y;
  1248. INTERSECTION *Best_Intersection;
  1249. OBJECT **Best_Object;
  1250. {
  1251.   INTERSECTION New_Intersection;
  1252.   unsigned short i;
  1253.   int Found;
  1254.   RAYINFO rayinfo;
  1255.   DBL key;
  1256.   BBOX_TREE *BBox_Node;
  1257.   PROJECT_TREE_NODE *Node;
  1258.  
  1259.   /* If there's no vista tree then return. */
  1260.  
  1261.   if (Tree == NULL)
  1262.   {
  1263.     return(FALSE);
  1264.   }
  1265.  
  1266.   /* Start with an empty priority queue */
  1267.  
  1268.   VLBuffer_Queue->QSize = 0;
  1269.  
  1270.   Found = FALSE;
  1271.  
  1272. #ifdef BBOX_EXTRA_STATS
  1273.   Increase_Counter(stats[totalQueueResets]);
  1274. #endif
  1275.  
  1276.   /* Traverse the tree. */
  1277.  
  1278.   Node_Queue->QSize = 0;
  1279.  
  1280.   /* Create the direction vectors for this ray */
  1281.  
  1282.   Create_Rayinfo(Ray, &rayinfo);
  1283.  
  1284.   /* Fill the priority queue with all possible candidates */
  1285.  
  1286.   /* Check root */
  1287.  
  1288.   Increase_Counter(stats[LBuffer_Tests]);
  1289.  
  1290.   if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  1291.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  1292.   {
  1293.     Increase_Counter(stats[LBuffer_Tests_Succeeded]);
  1294.  
  1295.     Node_Queue->Queue[(Node_Queue->QSize)++] = Tree;
  1296.   }
  1297.  
  1298.   /* Loop until queue is empty. */
  1299.  
  1300.   while (Node_Queue->QSize > 0)
  1301.   {
  1302.     Tree = Node_Queue->Queue[--(Node_Queue->QSize)];
  1303.  
  1304.     if (Tree->is_leaf)
  1305.     {
  1306.       /* Leaf --> test object's bounding box in 3d */
  1307.  
  1308.       Check_And_Enqueue(VLBuffer_Queue,
  1309.         ((PROJECT_TREE_LEAF *)Tree)->Node,
  1310.         &((PROJECT_TREE_LEAF *)Tree)->Node->BBox, &rayinfo);
  1311.     }
  1312.     else
  1313.     {
  1314.       /* Check siblings of the node in 2d */
  1315.  
  1316.       for (i = 0; i < Tree->Entries; i++)
  1317.       {
  1318.         Node = Tree->Entry[i];
  1319.  
  1320.         Increase_Counter(stats[LBuffer_Tests]);
  1321.  
  1322.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  1323.             (y >= Node->Project.y1) && (y <= Node->Project.y2))
  1324.         {
  1325.           Increase_Counter(stats[LBuffer_Tests_Succeeded]);
  1326.  
  1327.           /* Reallocate queues if they're too small. */
  1328.  
  1329.           Reinitialize_VLBuffer_Code();
  1330.  
  1331.           /* Add node to node queue */
  1332.  
  1333.           Node_Queue->Queue[(Node_Queue->QSize)++] = Node;
  1334.         }
  1335.       }
  1336.     }
  1337.   }
  1338.  
  1339.   /* Now test the candidates in the priority queue */
  1340.  
  1341.   while (VLBuffer_Queue->QSize > 0)
  1342.   {
  1343.     Priority_Queue_Delete(VLBuffer_Queue, &key, &BBox_Node);
  1344.  
  1345.     if (key > Best_Intersection->Depth)
  1346.     {
  1347.       break;
  1348.     }
  1349.  
  1350.     if (Intersection(&New_Intersection, (OBJECT *)BBox_Node->Node, Ray))
  1351.     {
  1352.       if (New_Intersection.Depth < Best_Intersection->Depth)
  1353.       {
  1354.         *Best_Intersection = New_Intersection;
  1355.  
  1356.         *Best_Object = (OBJECT *)BBox_Node->Node;
  1357.  
  1358.         Found = TRUE;
  1359.       }
  1360.     }
  1361.   }
  1362.  
  1363.   return(Found);
  1364. }
  1365.  
  1366.  
  1367.  
  1368.